
\section{Related Work}

\noindent \textbf{Security via Diversifying.} As suggested by
Forrest et al.~\cite{Forrest}, randomization can be introduced to
computer system to create the diversity of the software. There are a
large number of randomization techniques, including Address Space
Randomization (ASR), Instruction Set Randomization (ISR), Data Space
Randomization (DSR), and System Interface Randomization (SIR).

ASR~\cite{ASLR1,ASLR2,ASLR3} is a technique to randomize the base
address of the stack, heap, shared libraries, or even program
images. It has become a standard component in many operating systems
including Linux, Windows and Mac OS. Although ASR can be used to
prevent the attacker predicting the absolute base address of the
memory area (stack, or heap)~\cite{ASLR1,ASLR2} or even the relative
distance between the objects\cite{ASLR3}, they cannot protect the
fine-grained internal data structure. Also, researchers have found a
number of ways~\cite{deASLR1,deASLR2,deASLR3} to circumvent the
protection of ASR. ISR is an approach to preventing code injection
attacks by randomizing the underlying instructions
\cite{ISrand,ISrand1}. In this scheme, all the instructions are
decrypted during execution and thus the injected code will not be
properly decrypted. Similar to ASR which can be bypassed, Sovarel et
al.~\cite{deISR} recently proposed a method to circumvent the ISR.
DSR~\cite{DSR,Pointguard,dr} is a technique to encrypt the memory
objects. For example, PointGuard~\cite{Pointguard} encrypts the
program pointers, and techniques in~\cite{DSR,dr} provides a
probabilistic protection against memory exploits by XORing data with
random masks. The difference compared to SALADS is DSR is a
field-insensitive analysis, whereas the focus of SALDAS is the
fine-grained data structure field. SIR provides the randomization of
system interfaces, such as system
call~\cite{Dawn:OS:Random:technical:report, RandSys} in operating
system and hypercall~\cite{Cnong09} in hypervisor. However, these
methods cannot protect the security sensitive data structure.

%However, DSR focuses on the memory exploits, but can not prevent
%the rootkits. In addition, data space randomization depends on the
%field-insensitive points-to analysis, which cannot handle the
%memory exploits within the data structure (the main focus of our
%work).

 %SALADS is the
%supplement to the existing randomization techniques. Its purpose is
%protecting the data structure from being maliciously read/written.
%

\vspace{0.1in} \noindent \textbf{Data Structure Layout
Randomization.} SALADS shares some similarity to data structure
layout reorder, which has been designed on different compilers to
improve the performance of the program, including
GCC~\cite{GCC1,GCC2,GCC3,Pointguard} and Open64 Compiler~\cite{111}.
There are a number of data structure layout reorder techniques with
slightly different goals, for example, Dannowski et
al.~\cite{dannowski07automated} proposed the method to optimize the
object layout in a portable microkernel; Lattner et
al.~\cite{Lattner} focused on the pointer-based data structure to
speed up the C programs; Golovanevsky et al.~\cite{file} proposed
the optimization method for the multi-core processors. % The Data
%Structure layout reorder method contains structure peeling,
%structure splitting and structure reordering. But
%All these reorder methods mainly focus on improving the performance of the programs.

Recently, DSLR~\cite{Dimva'09} has been proposed for security
purposes. DSLR modifies the definition of the data structure to
reorder the fields. However, as discussed earlier DSLR has several
limitations including the seed for the data structure is fixed at
compilation time, and it involves manual efforts to determine which
data structure can be randomized. Most recently, Xin et
al.~\cite{ISC10} extends DSLR and proposed using a constraint set
for selecting which data structure to be randomized. But their
techniques also have a number of limitations. First they cannot
handle the nested data structures (which are very common in Linux
kernel data structure), second they ignore all the data structure
related to the pointer arithmetic operations and API parameter, and
third their randomization key will not be changed once the software
is compiled.

%
%
%\vspace{0.1in} \noindent \textbf{Other Data Structure Related Works.}
%Data structure is so security sensitive that it raises many
%problems. On the one hand, it encapsulates the key information of
%the program. For example, the heap metadata
%(\texttt{malloc\_chunk}), the process information
%(\texttt{task\_struct}). If the attacks aim at these data structure
%(e.g.,rootkits modifies the \texttt{task\_struct}, malware modifies
%the \texttt{malloc\_chunk}), they will introduce the stealthy
%behavior. On the other hand, data structure discloses the
%characteristic of the malware, some reverse engineering tools (both
%the dynamic method\cite{Howard, Rewards:NDSS10} and static method
%\cite{Siggraph}) do memory forensic on the data structure, and some
%malware detection tools use the data structure as the signature
%\cite{Laika}. However, SALADS can be applied to the malicious
%programs and enable them diverse the data structure memory layout
%from time to time, as such the randomized malicious code is hard to
%be detected. Although our method is benign purpose, the potential
%threats triggers the detection or froensic tools to improve.
